package codetop.microsoft.T84;

import util.ListUtil;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: 18362
 * @Create: 2022-08-15 21:34:47 星期一
 */
class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> dq = new LinkedList<>();
        int[] left = new int[heights.length], right = new int[heights.length];
        for (int i=heights.length-1; i>=0; --i) {
            while (!dq.isEmpty() && heights[dq.getLast()] >= heights[i])
                dq.removeLast();
            left[i] = dq.isEmpty() ? heights.length : dq.getLast();
            dq.addLast(i);
        }
        dq.clear();
        for (int i=0; i<heights.length; ++i) {
            while (!dq.isEmpty() && heights[dq.getLast()] >= heights[i])
                dq.removeLast();
            right[i] = dq.isEmpty() ? -1 : dq.getLast();
            dq.addLast(i);
        }
        int res = Integer.MIN_VALUE;
        for (int i=0; i<heights.length; ++i) {
            int area = (left[i] - right[i] - 1) * heights[i];
            res = Math.max(res, area);
        }
        return res;
    }
}